home *** CD-ROM | disk | FTP | other *** search
/ GFX Sensations 1 / Graphic Sensations - Volume 1.iso / tools / amiga / 3d_tools / irit40s.lha / Irit / cagd_lib / cbzreval.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-30  |  9.5 KB  |  289 lines
  1. /******************************************************************************
  2. * CBzrEval.c - Bezier curves handling routines - evaluation routines.          *
  3. *******************************************************************************
  4. * Written by Gershon Elber, Mar. 90.                          *
  5. ******************************************************************************/
  6.  
  7. #include <ctype.h>
  8. #include <stdio.h>
  9. #include <string.h>
  10. #include "cagd_loc.h"
  11.  
  12. static int BezierCacheEnabled = FALSE;
  13. static int CacheFineNess = 0, PowerCacheFineNess;
  14. static CagdRType *BezierCache[CAGD_MAX_BEZIER_CACHE_ORDER + 1]
  15.                  [CAGD_MAX_BEZIER_CACHE_ORDER + 1];
  16.  
  17. static int IChooseK[CAGD_MAX_BEZIER_CACHE_ORDER + 1]
  18.            [CAGD_MAX_BEZIER_CACHE_ORDER + 1] =
  19. {
  20.     {    1,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0  },
  21.     {    1,    1,    0,    0,    0,    0,    0,    0,    0,    0,    0  },
  22.     {    1,    2,    1,    0,    0,    0,    0,    0,    0,    0,    0  },
  23.     {    1,    3,    3,    1,    0,    0,    0,    0,    0,    0,    0  },
  24.     {    1,    4,    6,    4,    1,    0,    0,    0,    0,    0,    0  },
  25.     {    1,    5,   10,   10,    5,    1,    0,    0,    0,    0,    0  },
  26.     {    1,    6,   15,   20,   15,    6,    1,    0,    0,    0,    0  },
  27.     {    1,    7,   21,   35,   35,   21,    7,    1,    0,    0,    0  },
  28.     {    1,    8,   28,   56,   70,   56,   28,    8,    1,    0,    0  },
  29.     {    1,    9,   36,   84,  126,  126,   84,   36,    9,    1,    0  },
  30.     {    1,   10,   45,  120,  210,  252,  210,  120,   45,   10,    1  }
  31. };
  32.  
  33. static CagdRType BzrCrvEvalFuncAux(int i, int k, CagdRType t);
  34. static CagdRType IntPow(CagdRType x, int i);
  35.  
  36. /******************************************************************************
  37. * Sets the bezier sampling cache - if enabled, a bezier can be evaluated      *
  38. * directly from pre sampled basis function.                      *
  39. ******************************************************************************/
  40. void BzrCrvSetCache(int FineNess, CagdBType EnableCache)
  41. {
  42.     int i, j, k;
  43.  
  44.     if (BezierCacheEnabled == EnableCache && FineNess == CacheFineNess)
  45.     return;
  46.  
  47.     if (BezierCacheEnabled) {
  48.     /* Free old cache if was one. */
  49.     for (k = 2; k <= CAGD_MAX_BEZIER_CACHE_ORDER; k++)
  50.         for (i = 0; i < k; i++)
  51.         if (BezierCache[k][i] != NULL) {
  52.             IritFree((VoidPtr) BezierCache[k][i]);
  53.             BezierCache[k][i] = NULL;
  54.         }
  55.     }
  56.  
  57.     if ((BezierCacheEnabled = EnableCache) != FALSE) {
  58.     /* Allocate the new cache and initalize it: */
  59.     if (FineNess < 2)
  60.         FineNess = 2;
  61.     if (FineNess > CAGD_MAX_BEZIER_CACHE_FINENESS)
  62.         FineNess = CAGD_MAX_BEZIER_CACHE_FINENESS;
  63.     CacheFineNess = FineNess;
  64.     PowerCacheFineNess = 1 << FineNess;
  65.  
  66.     for (k = 2; k <= CAGD_MAX_BEZIER_CACHE_ORDER; k++)/* For all orders. */
  67.         for (i = 0; i < k; i++) {      /* Allocate and set all basis func. */
  68.         BezierCache[k][i] = (CagdRType *)
  69.             IritMalloc(sizeof(CagdRType) * PowerCacheFineNess);
  70.         for (j = 0; j < PowerCacheFineNess; j++)
  71.             BezierCache[k][i][j] = BzrCrvEvalFuncAux(i, k,
  72.                 ((CagdRType) j) / (PowerCacheFineNess - 1));
  73.         }
  74.     }
  75. }
  76.  
  77. /******************************************************************************
  78. * Assumes Vec holds control points for scalar bezier curve of order Order,    *
  79. * and evaluates and returns that curve value at parameter value t.          *
  80. * Vec is incremented by VecInc (usually by 1) after each iteration.          *
  81. ******************************************************************************/
  82. CagdRType BzrCrvEvalVecAtParam(CagdRType *Vec, int VecInc, int Order, CagdRType t)
  83. {
  84.     int i;
  85.     CagdRType R = 0.0;
  86.  
  87.     if (VecInc == 1)
  88.     for (i = 0; i < Order; i++)
  89.         R += BzrCrvEvalFuncAux(i, Order, t) * *Vec++;
  90.     else
  91.     for (i = 0; i < Order; i++) {
  92.         R += BzrCrvEvalFuncAux(i, Order, t) * *Vec;
  93.         Vec += VecInc;
  94.     }
  95.  
  96.     return R;
  97. }
  98.  
  99. /******************************************************************************
  100. * Returns a pointer to a static data, holding the value of the curve at given *
  101. * parametric location t. The curve is assumed to be Bezier.              *
  102. ******************************************************************************/
  103. CagdRType *BzrCrvEvalAtParam(CagdCrvStruct *Crv, CagdRType t)
  104. {
  105.     static CagdRType Pt[CAGD_MAX_PT_COORD];
  106.     CagdBType
  107.     IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv);
  108.     int i, j,
  109.     k = Crv -> Order,
  110.     MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
  111.     CagdRType B;
  112.  
  113.     for (j = IsNotRational; j <= MaxCoord; j++)
  114.     Pt[j] = 0.0;
  115.  
  116.     for (i = 0; i < k; i++) {
  117.     B = BzrCrvEvalFuncAux(i, k, t);
  118.     for (j = IsNotRational; j <= MaxCoord; j++)
  119.         Pt[j] += B * Crv -> Points[j][i];
  120.     }
  121.  
  122.     return Pt;
  123. }
  124.  
  125. /******************************************************************************
  126. * Samples the curves at FineNess location equally spaced in the Bezier        *
  127. * parametric domain [0..1]. If Cache is enabled, and FineNess is power of     *
  128. * two, upto or equal to CacheFineNess, the cache is used, otherwise the       *
  129. * points are evaluated manually for each of the samples.              *
  130. * Data is saved at the Points array of vectors (according to Curve PType),    *
  131. * each vector is assumed to be allocated for FineNess CagdRType points.          *
  132. ******************************************************************************/
  133. void BzrCrvEvalToPolyline(CagdCrvStruct *Crv, int FineNess,
  134.                             CagdRType *Points[])
  135. {
  136.     CagdBType
  137.     UseCache = BezierCacheEnabled &&
  138.            FineNess == CacheFineNess &&
  139.            Crv -> Order <= CAGD_MAX_BEZIER_CACHE_ORDER,
  140.     IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv);
  141.     int i, j, Count,
  142.     k = Crv -> Order,
  143.     MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
  144.     CagdRType B;
  145.  
  146.     if (UseCache) {
  147.     for (Count = 0; Count < PowerCacheFineNess; Count++) {
  148.         for (j = IsNotRational; j <= MaxCoord; j++)
  149.         Points[j][Count] = 0.0;
  150.         for (i = 0; i < k; i++) {
  151.         B = BezierCache[k][i][Count];
  152.         for (j = IsNotRational; j <= MaxCoord; j++)
  153.             Points[j][Count] += B * Crv -> Points[j][i];
  154.         }
  155.     }
  156.     }
  157.     else {
  158.     FineNess = 1 << FineNess;
  159.     for (Count = 0; Count < FineNess; Count++) {
  160.         for (j = IsNotRational; j <= MaxCoord; j++)
  161.         Points[j][Count] = 0.0;
  162.         for (i = 0; i < k; i++) {
  163.         B = BzrCrvEvalFuncAux(i, k,
  164.                       ((CagdRType) Count) / (FineNess - 1));
  165.         for (j = IsNotRational; j <= MaxCoord; j++)
  166.             Points[j][Count] += Crv -> Points[j][i] * B;
  167.         }
  168.     }
  169.     }
  170. }
  171.  
  172. /******************************************************************************
  173. * Evaluate the i bezier function of order k, at parametric value t          *
  174. * (t in [0..1]).                                  *
  175. * This function is:           i     k - i - 1          i              *
  176. *            Bi,k(t) = ( ) * t          * (1 - t)              *
  177. *                   k                          *
  178. ******************************************************************************/
  179. static CagdRType BzrCrvEvalFuncAux(int i, int k, CagdRType t)
  180. {
  181.     if (APX_EQ(t, 0.0))
  182.     return (CagdRType) (i == 0);
  183.     else if (APX_EQ(t, 1.0))
  184.     return (CagdRType) (i == k - 1);
  185.     else
  186.     return (k >= CAGD_MAX_BEZIER_CACHE_ORDER ?
  187.             CagdIChooseK(i, k - 1) : (CagdRType) IChooseK[k - 1][i]) *
  188.            IntPow(1.0 - t, k - i - 1) * IntPow(t, i);
  189. }
  190.  
  191. /******************************************************************************
  192. * Computes x to the power of i, i integer.                      *
  193. ******************************************************************************/
  194. static CagdRType IntPow(CagdRType x, int i)
  195. {
  196.     CagdRType Power, RetVal;
  197.  
  198.     for (Power = x, RetVal = 1.0; i != 0; i >>= 1) {
  199.     if (i & 0x01)
  200.        RetVal *= Power;
  201.     
  202.     Power = SQR(Power);
  203.     }
  204.  
  205.     return RetVal;
  206. }
  207.  
  208. /******************************************************************************
  209. * Evaluate the following (in floating point arithmetic):              *
  210. *             k         k!                          *
  211. *            ( ) = -------------                      *
  212. *             i    i! * (k - i)!                      *
  213. ******************************************************************************/
  214. CagdRType CagdIChooseK(int i, int k)
  215. {
  216.     int j;
  217.     CagdRType
  218.     c = 1.0;
  219.  
  220.     if ((k >> 1) > i) {                /* i is less than half of k: */
  221.     for (j = k - i + 1; j <= k; j++)
  222.         c *= j;
  223.     for (j = 2; j <= i; j++)
  224.         c /= j;
  225.     }
  226.     else {
  227.     for (j = i + 1; j <= k; j++)
  228.         c *= j;
  229.     for (j = 2; j <= k - i; j++)
  230.         c /= j;
  231.     }
  232.  
  233.     return c;
  234. }
  235.  
  236. #ifdef K_CHOOSE_I_GEN
  237.  
  238. /******************************************************************************
  239. * Evaluate the following (in integer arithmetic):                  *
  240. *             k         k!                          *
  241. *            ( ) = -------------                      *
  242. *             i    i! * (k - i)!                      *
  243. ******************************************************************************/
  244. static int IChooseKGenOne(int i, int k)
  245. {
  246.     int j;
  247.     long c = 1;
  248.  
  249.     if ((k >> 1) > i) {                /* i is less than half of k: */
  250.     for (j = k - i + 1; j <= k; j++)
  251.         c *= j;
  252.     for (j = 2; j <= i; j++)
  253.         c /= j;
  254.     }
  255.     else {
  256.     for (j = i + 1; j <= k; j++)
  257.         c *= j;
  258.     for (j = 2; j <= k - i; j++)
  259.         c /= j;
  260.     }
  261.  
  262.     return (int) c;
  263. }
  264.  
  265. /******************************************************************************
  266. * Evaluate IChooseK for all possiblities and print them for the              *
  267. * IChooseK table defined in the beginning of this file.                  *
  268. ******************************************************************************/
  269. void IChooseKGen(void)
  270. {
  271.     int i, j;
  272.  
  273.     for (i = 0; i <= MAX_BEZIER_CACHE_ORDER; i++) {
  274.     printf(" },\n    {");
  275.     for (j = 0; j <= MAX_BEZIER_CACHE_ORDER; j++)
  276.         printf(" %4d,", j <= i ? IChooseKGenOne(j ,i) : 0);
  277.     }
  278. }
  279.  
  280. /******************************************************************************
  281. * main to create the table in the befinning of this file.              *
  282. ******************************************************************************/
  283. void main(void)
  284. {
  285.     IChooseKGen();
  286. }
  287.  
  288. #endif /* K_CHOOSE_I_GEN */
  289.